package 算法.分治法.快排;

import java.util.Arrays;

public class QS2 {
    public static void main(String[] args) {
//        int arr[] = {2,3,4,5,6,7,822,3,4,5,8,6,5,4,2,1,-1,-1};
        int[] arr=new int[]{0,1,2,4,5,1,12,2,444,1321,12,1234134,143241,-1,7,7,7,7,7,-1,-100,3,3,3};
//        int[] arr=new int[]{3,1,2};
        arr=qsort2(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

    }
    private static int[]  qsort2(int arr[],int start,int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i<j) {
            while ((i<j) && (arr[j]>pivot)) {
                j--;
            }
            while ((i<j) && (arr[i]<pivot)) {
                i++;
            }
            if ((arr[i] == arr[j]) && (i<j)) {
                i++;
            } else {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if (i-1>start)//只剩下两个数了，而且i是基准点（左边肯定小于右边）
            arr=qsort2(arr,start,i-1);
        if (i+1<end)//只剩下两个数了，而且i是基准点（右边肯定小于左边）
            arr=qsort2(arr,i+1,end);
        return arr;
    }
}
